package org.gushi.algorithm.a03;

/**
 * 一、什么是堆
 * 堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。
 * Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
 *
 * 堆可以分为大顶堆和小顶堆。
 * 大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
 * 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
 *
 * 如果是排序，求升序用大顶堆，求降序用小顶堆。
 *
 * 一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现，
 * 最大的 K 个：小顶堆
 * 最小的 K 个：大顶堆
 *
 * 二、大顶堆的构建过程
 * 大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整。
 *
 * 最后一个非叶子节点怎么找？这里我们用数组表示待排序序列，则最后一个非叶子结点的位置是：数组长度/2-1。假如数组长度为9，则最后一个非叶子结点位置是 9/2-1=3。
 *
 * 比较当前结点的值和左子树的值，如果当前节点小于左子树的值，就交换当前节点和左子树；
 * 交换完后要检查左子树是否满足大顶堆的性质，不满足则重新调整子树结构；
 *
 * 再比较当前结点的值和右子树的值，如果当前节点小于右子树的值，就交换当前节点和右子树；
 * 交换完后要检查右子树是否满足大顶堆的性质，不满足则重新调整子树结构；
 *
 * 无需交换调整的时候，则大顶堆构建完成。
 */


/**
 * 三、大顶堆的排序过程
 * 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。
 *
 * 是不是对上面这一大段文字很头疼？其实排序过程用下面 4 步就能概括：
 * 第 1 步：先 n 个元素的无序序列，构建成大顶堆
 * 第 2 步：将根节点与最后一个元素交换位置，（将最大元素"沉"到数组末端）
 * 第 3 步：交换过后可能不再满足大顶堆的条件，所以需要将剩下的 n-1 个元素重新构建成大顶堆
 * 第 4 步：重复第 2 步、第 3 步直到整个数组排序完成。
 * ————————————————
 * 版权声明：本文为CSDN博主「卜思凡」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/a534469632/article/details/108316378
 */
public class Main {


    public static void main(String[] args) {

        int[] integers = new int[]{3, 7, 16, 10, 21, 23};

        HeapSort heapSort = new HeapSort(integers);
        heapSort.listSort();
//        for (int i = 0; i < integers.length; i++) {
//            System.out.print(integers[i]);
//            System.out.print(",");
//        }

    }


}
